﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace eu.h8me.Parsing.LexerLib {

    // DFA state helper.
    internal class NFAStateSet {

        // Content.
        SortedDictionary<Node, bool> _States = new SortedDictionary<Node, bool>();
        private int? _Hash;

        // Constructor.
        public NFAStateSet() {
            // No specific construction.
        }

        // Add a node.
        public void Add(Node node) {
            // Add the node to our set and return immediately if it's already present (all epsilon transitions are, too).
            if( _Hash.HasValue )
                throw new ArgumentException("Trying to add node to DFAState after hash computed");
            else if( _States.ContainsKey(node) )
                return;

            // Attach base node and walk while there are other nodes to add.
            Stack<Node> toadd = new Stack<Node>(node.EpsilonTransitions);
            _States[node] = true;
            while( toadd.Count > 0 ) {
                // Attach the node and check whether it's already present. If not, add all epsilon transitions to set.
                Node newnode = toadd.Pop();
                if( !_States.ContainsKey(newnode) ) {
                    // Wasn't present; process all epsilon transitions.
                    _States[newnode] = true;
                    foreach( Node epstrans in newnode.EpsilonTransitions )
                        toadd.Push(epstrans);
                }
            }
        }

        // Check for containment.
        public bool Contains(Node nod) {
            // Check whether the node is present in array.
            return _States.ContainsKey(nod);
        }

        // Hashing.
        public override int GetHashCode() {
            // Check whether hash code is set up.
            if( !_Hash.HasValue ) {
                // Set it up.
                int hash = 0;
                foreach( Node nod in _States.Keys )
                    hash = ( ( hash << 5 ) | ( hash >> 27 ) ) ^ nod.GetHashCode();

                // Set up hash.
                _Hash = hash;
            }

            // Return hash.
            return _Hash.Value;
        }

        // Equivalence testing.
        public override bool Equals(object obj) {
            // Check whether it's of proper type and then check contents.
            NFAStateSet other = obj as NFAStateSet;
            if( other == null || ( _Hash.HasValue && other._Hash.HasValue && _Hash.Value != other._Hash.Value ) ||
                _States.Count != other._States.Count )
                return false;

            // Compare states.
            IEnumerator<KeyValuePair<Node, bool>>[] dicts = new IEnumerator<KeyValuePair<Node, bool>>[] {
                _States.GetEnumerator(), other._States.GetEnumerator()
            };
            while( dicts[0].MoveNext() && dicts[1].MoveNext() )
                // Check entry for equivalence.
                if( dicts[0].Current.Key != dicts[1].Current.Key )
                    return false;

            // Compared equal, as they are equally long, they are equal.
            return true;
        }

        // Transitions.
        public IEnumerable<NFATransition> Transitions() {
            // Initialize state stack (i.e., node list and indices into transitions).
            int baseval = CharRange.MIN_VALUE;
            List<Node> nodes = new List<Node>();
            Dictionary<Node, int> idx = new Dictionary<Node, int>();
            HashSet<Node> curnodes = new HashSet<Node>();

            // Only process nodes that are actually applicable.
            foreach( Node nod in _States.Keys ) {
                if( nod.HasTransition ) {
                    // Has transition, so add it.
                    nodes.Add(nod);
                    idx[nod] = 0;
                }
            }

            // Next values.
            int nextval;
            List<Node> nodechange = new List<Node>();
            do {
                // Walk over all contained ranges.
                nextval = CharRange.MAX_VALUE;
                nodechange.Clear();
                foreach( Node nextnod in nodes ) {
                    // Check whether this node is eligible.
                    int nextidx = idx[nextnod];
                    if( 2 * nextnod.Transition.Chars.Count == nextidx )
                        continue;

                    // Check whether the value is smaller.
                    if( nextnod.Transition.Chars[nextidx >> 1][nextidx & 1] < nextval ) {
                        // This node is a unique point; clear sets and set up next base value.
                        nextval = nextnod.Transition.Chars[nextidx >> 1][nextidx & 1];
                        nodechange.Clear();
                        nodechange.Add(nextnod);
                    } else if( nextnod.Transition.Chars[nextidx >> 1][nextidx & 1] == nextval )
                        // This node changes transition at the same time another does, which is already setup.
                        nodechange.Add(nextnod);
                }

                // Check whether we should yield anything.
                if( baseval < nextval && curnodes.Count > 0 )
                    yield return new NFATransition(new Range(baseval, nextval), curnodes);

                // Update state.
                baseval = nextval;
                foreach( Node updnod in nodechange ) {
                    // Add to set and increment index.
                    if( ( idx[updnod]++ & 1 ) == 1 ) {
                        // Is currently present and will be removed at the end of this set.
                        bool removed = curnodes.Remove(updnod.Transition.Destination);
                        Debug.Assert(removed, "Node scheduled for remove but not present?");
                    } else {
                        // Is currently not present and will be present in the next set.
                        bool added = curnodes.Add(updnod.Transition.Destination);
                        Debug.Assert(added, "Node scheduled for add but present?");
                    }
                }
            } while( baseval != CharRange.MAX_VALUE );
        }

    }

    // NFA transition.
    internal class NFATransition {

        // Data.
        private Range _Range;
        private NFAStateSet _State = new NFAStateSet();

        // Constructor.
        public NFATransition(Range range, IEnumerable<Node> states) {
            // Store data and initialize state.
            _Range = range;
            foreach( Node nod in states )
                _State.Add(nod);
        }

        // Fetch range.
        public Range Range {
            get {
                // Return range.
                return _Range;
            }
        }

        // Fetch target state.
        public NFAStateSet State {
            get {
                // Return state.
                return _State;
            }
        }

    }

}
